#include "apue.h"
#include <pthread.h>
#include <limits.h>
#include <sys/time.h>
#include <stdlib.h>

#define NTHR 8
#define NUMNUM 8000000L
#define TNUM (NUMNUM / NTHR)

long nums[NUMNUM];
long snums[NUMNUM];

pthread_barrier_t b;

#ifdef SOLARIS
#define heapsort qsort
#else
extern int heapsort(void *, size_t, size_t, int (*)(const void *, const void *));
#endif

int complong(const void *arg1, const void *arg2) {
    long l1= *(long *)arg1;
    long l2= *(long *)arg2;
    if (l1 == l2)
        return 0;
    else if (l1 < l2)
        return -1;
    
    return 1;
}

void *thr_fn(void *arg) {
    long idx= (long)arg;
    heapsort(&nums[idx], TNUM, sizeof(long), complong);
    pthread_barrier_wait(&b);
    /* Go off and perform more work */
    return ((void *)0);
}

/**
 * Merge the results of the individual sorted ranges
 */
void merge() {
    long idx[NTHR];
    long i, minidx, sidx, num;
    for (i=0; i<NTHR; ++i)
        idx[i]= i*TNUM;
    for (sidx=0; sidx<NUMNUM; ++sidx) {
        num= LONG_MAX;
        for (i=0; i<NTHR; ++i) {
            if ((idx[i] < (i+1)*TNUM) && nums[idx[i]] < num) {
                minidx= i;
                num= nums[idx[i]];
            }
        }
        snums[sidx]= num;
        idx[minidx]++;
    }
}

int main() {
    unsigned long i;
    struct timeval start, end;
    long long startusec, endusec;
    double elapsed;
    int err;
    pthread_t tid;

    gettimeofday(&start, NULL);
    pthread_barrier_init(&b,  NULL, NTHR + 1);
    srandom(1);
    for (i=0; i<NUMNUM; ++i)
        nums[i]= random();

    for (i=0; i<NTHR; i++) {
        err= pthread_create(&tid, NULL, thr_fn, (void *)(i * TNUM));
        if (err != 0)
            err_exit(err, "cant create thread");
    }

    pthread_barrier_wait(&b);
    merge();
    gettimeofday(&end, NULL);
    startusec= (start.tv_sec * 1000000L + start.tv_usec);
    endusec= (end.tv_sec * 1000000L + end.tv_usec);
    printf("sort took %.4f\n", (endusec-startusec) / 1000000.0);

}
